package com.heima.leetcode.practice;

/**
 * @author 勾新杰
 * @version 1.0
 * @description: leetcode 31. 下一个排列
 * @date 2024/12/8 11:53
 */
public class E31 {

    /**
     * <h3>方法一：先找到第一个升序对，然后在升序对后面的降序范围中找出最小的大于nums[i]的元素与i交换，再对降序范围进行反转</h3>
     *
     * @param nums 上一个排列
     */
    public void nextPermutation1(int[] nums) {
        // 1. 查找从右到左第一个出现的升序对
        int i = nums.length - 2;
        while (i >= 0 && nums[i] >= nums[i + 1]) {
            i--;
        }
        // 升序对：i、i+1，那么i+1之后的就是非递增的，可以想象为降序的
        // 要找到最近的大于当前数组形成数字的最小数字，应该尽量不动高位，多动低位
        // 2. 如果找到这样的升序对，则在i+1之后找到大于nums[i]的最小数字，与i交换
        if (i >= 0) {
            int j = i + 1;
            while (j < nums.length && nums[j] > nums[i]) {
                j++;
            }
            swap(nums, i, j - 1);
        }
        // 3. 最后反转i+1之后的数组即可，没找到升序对也能处理，就是反转整个数组
        reverse(nums, i + 1, nums.length - 1);
    }

    /**
     * <h3>方法二：对方法一的代码进行优化，更好理解一些，本质一样</h3>
     *
     * @param nums 上一个排列
     */
    public void nextPermutation2(int[] nums) {
        // 1. 求出从右往左第一个升序对的左边的元素的索引
        int index = -1;
        for (int i = nums.length - 2; i >= 0; i--) {
            if (nums[i] < nums[i + 1]) {
                index = i;
                break;
            }
        }
        // 2. 如果索引是-1，也就是没有升序对，说明数组是完全降序的，直接反转整个数组即可
        if (index == -1) {
            reverse(nums, 0, nums.length - 1);
            return;
        }
        // 3. 在[index + 1, nums.length - 1]降序范围之间找到第一个大于nums[index]的最小数字，与index交换，再反转index + 1, nums.length - 1之间的数组即可
        for (int i = index + 1; i < nums.length; i++) {
            if (nums[i] > nums[index]
                    && (i + 1 == nums.length || nums[i + 1] <= nums[index])) {
                swap(nums, index, i);
                reverse(nums, index + 1, nums.length - 1);
                break;
            }
        }
    }

    /**
     * 交换数组中两个元素的值
     *
     * @param nums   数组
     * @param index1 第一个下标
     * @param index2 第二个下标
     */
    private void swap(int[] nums, int index1, int index2) {
        int temp = nums[index1];
        nums[index1] = nums[index2];
        nums[index2] = temp;
    }

    /**
     * 反转数组中从begin到end之间的元素
     *
     * @param nums  数组
     * @param begin 开始下标（包含）
     * @param end   结束下标（包含）
     */
    private void reverse(int[] nums, int begin, int end) {
        while (begin < end) { // begin == end的时候不需要交换
            swap(nums, begin, end);
            begin++;
            end--;
        }
    }
}
